#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/4/12 22:13|22:13
# @Author  : yangdingyi
# @File    : 面试题 16.03. 交点.2020-04-12
# @Software: PyCharm
from typing import List


class Solution:
    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
        a, b = start1, end1
        c, d = start2, end2

        def area(x, y, z):
            return (x[0] - z[0]) * (y[1] - z[1]) - (x[1] - z[1]) * (y[0] - z[0])

        # area_abc = (a[0] - c[0]) * (b[1] - c[1]) - (a[1] - c[1]) * (b[0] - c[0])
        area_abc = area(a, b, c)
        # print('abc', area_abc)
        # area_abd = (a[0] - d[0]) * (b[1] - d[1]) - (a[1] - d[1]) * (b[0] - d[0])
        area_abd = area(a, b, d)
        # print('abd', area_abd)
        if area_abc * area_abd > 0:
            return []
        area_cda = area(c, d, a)
        # print('cda', area_cda)
        area_cdb = area_cda + area_abc - area_abd
        # print('cdb', area_cdb)

        if area_cda * area_cdb > 0:
            return []

        if area_abd - area_abc == 0:
            xs = [(0, a), (0, b), (1, c), (1, d)]
            xs.sort(key=lambda x: x[1][0] * 1000 + x[1][1])
            if xs[0][0] != xs[1][0]:
                return xs[1][1]
            return []

        t = area_cda / (area_abd - area_abc)
        dx = t * (b[0] - a[0])
        dy = t * (b[1] - a[1])

        return [a[0] + dx, a[1] + dy]


solve = Solution()
q1s1, q1e1 = [0, 0], [1, 0]
q1s2, q1e2 = [1, 1], [0, -1]
print(q1s1, q1e1)
print(q1s2, q1e2)
print(solve.intersection(q1s1, q1e1, q1s2, q1e2))

q2s1, q2e1 = [0, 3], [0, 6]
q2s2, q2e2 = [0, 1], [0, 5]
print(q2s1, q2e1)
print(q2s2, q2e2)
print(solve.intersection(q2s1, q2e1, q2s2, q2e2))

